package Linklist;

import java.util.List;

/**
 * @Classname JZ77单链表排序
 * @Description TODO
 * @Date 2023/2/10 9:07
 * @Created by xjl
 */
public class JZ77单链表排序 {

    class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val=val;
        }
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode head2 = slow.next;
        slow.next = null;
        ListNode list1 = sortList(head);
        ListNode list2 = sortList(head2);
        return merge(list1,list2);
    }

    private ListNode merge(ListNode node1, ListNode node2) {
        if (node1==null){
            return node2;
        }
        if (node2==null){
            return node1;
        }
        ListNode dump=new ListNode(-1);
        ListNode curr=dump;
        while (node1!=null&&node2!=null){
            if (node1.val<= node2.val){
                curr.next=node1;
                node1=node1.next;
            }else {
                curr.next=node2;
                node2=node2.next;
            }
            curr=curr.next;
        }
        curr.next=node1!=null?node1:node2;
        return dump.next;
    }
}
